package DP;

/**
 * @author 曹见朋
 * @create 2024-06-13-21:47
 */
public class Main213 {
    // TODO 213. 打家劫舍 II
    public static int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        return Math.max(sub(nums, 0, nums.length - 2), sub(nums, 1, nums.length - 1));
    }
    private static int sub(int[] nums, int start, int end){
        if(end - start == 0) return nums[start];
        if(end - start == 1) return Math.max(nums[start], nums[start + 1]);
        int[] dp = new int[end - start + 1];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);
        int index = 2;
        for(int i = start + 2; i <= end; i++){
            dp[index] = Math.max(dp[index - 1], dp[index - 2] + nums[i]);
            index++;
        }
        return dp[end - start];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,1};
        int rob = rob(nums);
        System.out.println(rob);
    }
}
